package PersonStu.sanqi;

/**
 * @Author: Dijah
 * @Date: 2022/12/7 17:28
 * @Desc: 雨水问题
 * 给定一个正整数数组arr，把arr想象成一个直方图。
 * 放回这个直方图如果能够装水，能装下几格水。
 * 3,2,1,6,5,1,2
 */
public class code_09_TrappingRainWater {

    public static int water(int [] arr){
        if(arr.length == 0 || arr == null){
            return 0;
        }
        int water = 0;
        int N = arr.length;
        int L = 1;
        int R = N - 2;
        int leftMax = arr[0];
        int rightMax = arr[N - 1];
        while (L <= R){
            if(leftMax <= rightMax){
                //左侧小于等于右侧的，
                //1、将water累加，并且比较大的那个值
                water += Math.max(0,leftMax-arr[L]);
                //2、leftMax重新定位
                leftMax = Math.max(arr[L++],leftMax);
            }else {
                water += Math.max(0,rightMax-arr[R]);
                rightMax = Math.max(rightMax,arr[R--]);
            }
        }

        return water;
    }

    public static void main(String[] args) {
        int [] arr = {1,8,6,2,5,4,8,3,7};
        int water = water(arr);
        System.out.println(water);
    }
}
